package com.ai.zuochengyun.phase01.class03;

/**
 * 最大的子搜索二叉树的大小
 */
public class Code23_MaxSubBSTSize {

    public static void main(String[] args) {

    }

    public static int maxSubBSTSize(BinaryTreeNode x) {
        if (x == null) {
            return 0;
        }
        return process(x).maxSubBSTSize;
    }

    public static Info process(BinaryTreeNode x) {
        if (x == null) {
           return null;
        }

        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        // 默认max和min为当前节点X的值
        int max = x.value;
        int min = x.value;
        // 默认整棵树就X这一个节点
        int allSize = 1;

        if (leftInfo != null) {
            // 当前值和左边的最大值进行pk，前值和左边的最小值进行pk
            max = Math.max(leftInfo.max, max);
            min = Math.min(leftInfo.min, min);
            allSize += leftInfo.allSize;
        }
        if (rightInfo != null) {
            // 当前值和右边的最大值进行pk，当前值和右边的最小值进行pk
            max = Math.max(rightInfo.max, max);
            min = Math.min(rightInfo.min, min);
            allSize += rightInfo.allSize;
        }

        // 列可能性 important!
        // p1表示左树最大的子搜索二叉树的大小
        int p1 = -1;
        if (leftInfo != null) {
            p1 = leftInfo.maxSubBSTSize;
        }
        // p2表示右树最大的子搜索二叉树的大小
        int p2 = -1;
        if (rightInfo != null) {
            p2 = rightInfo.maxSubBSTSize;
        }

        // 左子树和右子树要串联起来
        int p3 = -1;
        boolean leftBST = leftInfo == null || leftInfo.maxSubBSTSize == leftInfo.allSize;
        boolean rightBST = rightInfo == null || rightInfo.maxSubBSTSize == rightInfo.allSize;
        // 左右树都是搜索二叉树
        if (leftBST && rightBST) {
            // 针对以X为头的整个树是否是二叉树
            boolean x1 = leftInfo == null || leftInfo.max < x.value;
            boolean x2 = rightInfo == null || rightInfo.min > x.value;
            if (x1 && x2) {
                p3 = (leftInfo == null ? 0 : leftInfo.allSize) + (rightInfo == null ? 0 : rightInfo.allSize) + 1;
            }
        }
        int maxSubBSTSize = Math.max(p1, Math.max(p2, p3));
        return new Info(max, min, maxSubBSTSize, allSize);
    }

    public static class Info {
        public int max;

        public int min;

        // 最大子二叉树的大小
        public int maxSubBSTSize;

        // 整棵树的大小
        public int allSize;

        public Info(int max, int min, int maxSubBSTSize, int allSize) {
            this.max = max;
            this.min = min;
            this.maxSubBSTSize  = maxSubBSTSize;
            this.allSize = allSize;
        }
    }

}

